We've seen that for sparse graphs, an advanced $O(E \log V)$ algorithm is superior to the simple $O(V^2)$ approach. The key to this performance gain lies in optimizing the most expensive step: finding the next minimum-weight edge.

  • The bottleneck in the simple implementation is the linear scan through an array of $V$ vertices in every single iteration. To avoid this repeated scan, we can use a Priority Queue (PQ).
  • A Priority Queue is an abstract data structure with two main operations: insert(item, priority) and extract_min().
  • In Prim's algorithm, the PQ will store the "frontier" edges—those connecting a vertex in the MST to a vertex outside the MST. The edge weight serves as the priority.
  • This allows us to find the cheapest edge to add in $O(\log V)$ time instead of $O(V)$ time.
Python Implementation (heapq)
 1import heapq
 2
 3# The Priority Queue will store tuples of (weight, vertex_from, vertex_to)
 4# Python's heapq is a min-heap, perfect for our needs.
 5frontier_edges = []
 6
 7# Imagine we just added vertex 'A' to our MST.
 8# We add its adjacent edges to the PQ.
 9heapq.heappush(frontier_edges, (4, 'A', 'B'))
10heapq.heappush(frontier_edges, (3, 'A', 'C'))
11print(f"PQ after adding A's edges: {frontier_edges}")
12
13# Now, we extract the minimum-weight edge.
14# heapq.heappop() always returns the smallest item.
15min_edge = heapq.heappop(frontier_edges)
16print(f"Extracted min edge: {min_edge}")
17print(f"PQ after extraction: {frontier_edges}")